﻿#include "Heap.h"

void HeapInit(Heap* ph)
{
	//1. 传入的堆指针不能为空。
	assert(ph);

	//2. 将数组指针置空，容量和个数置0。
	ph->arr = NULL;
	ph->size = ph->capacity = 0;
}

void Swap(HeapDataType* h1, HeapDataType* h2)
{
	HeapDataType tmp = *h1;
	*h1 = *h2;
	*h2 = tmp;
}

void AdjustUp(HeapDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	//孩子到根位置结束
	while (child)
	{
		//1. 小堆：当孩子小于父亲，孩子和父亲的值交换。
		if (arr[child] < arr[parent]) Swap(&arr[child], &arr[parent]);
		//2. 如果孩子大于等于父亲就直接break不用比较了
		else break;

		//3. 孩子再走到父亲的位置继续向上比较
		child = parent;
		parent = (child - 1) / 2;
	}
}

void HeapPush(Heap* ph, HeapDataType data)
{
	//1. 传入的堆指针不能为空。
	assert(ph);

	//2. 插入前判断需不需要扩容。
	size_t capacity = ph->capacity == 0 ? 4 : ph->capacity * 2;
	HeapDataType* tmp = realloc(ph->arr, sizeof(HeapDataType) * capacity);
	if (tmp == NULL)
	{
		perror("realloc");
		return;
	}
	ph->arr = tmp;
	ph->capacity = capacity;

	//3. 最后一个位置插入，然后size++。
	ph->arr[ph->size++] = data;

	//4. 插入后使用向上调整算法。
	AdjustUp(ph->arr, ph->size - 1);
}

bool HeapEmpty(Heap* ph)
{
	//1. 传入的堆指针不能为空。
	assert(ph);

	//2. 判断size是否为0，空返回真。
	return ph->size == 0;
}

void AdjustDown(HeapDataType* arr, int size, int parent)
{
	//小堆：先假设左孩子是小的，再将左孩子和右孩子比一下，谁小谁就是child。记得判断一下右孩子是否存在。
	int child = parent * 2 + 1;
	while (child < size)
	{
		//1. 小堆：parent和较小的孩子比较
		if (child + 1 < size && arr[child + 1] < arr[child]) child++;

		//2. parent 和 child 比较，parent比child大就交换
		if (arr[parent] > arr[child]) Swap(&arr[parent], &arr[child]);
		else break;

		//3. 然后parent走到child的位置继续往下比较
		parent = child;
		child = parent * 2 + 1;
	}
}

void HeapPop(Heap* ph)
{
	//1. 传入的堆指针不能为空。
	assert(ph);
	//2. 堆不能为空。
	assert(!HeapEmpty(ph));

	//3. 删除是删堆顶的数据，先将堆顶数据和最后一个数据交换，然后删除最后一个数据。
	Swap(&ph->arr[0], &ph->arr[ph->size - 1]);
	ph->size--;

	//4. 从堆顶数据开始向下调整。
	AdjustDown(ph->arr, ph->size, 0);
}

HeapDataType HeapTop(Heap* ph)
{
	//1. 传入的堆指针不能为空。
	assert(ph);
	//2. 堆不能为空。
	assert(!HeapEmpty(ph));

	//3. 返回数组第一个元素。
	return ph->arr[0];
}

int HeapSize(Heap* ph)
{
	//1. 传入的堆指针不能为空。
	assert(ph);

	//2. 返回size。
	return ph->size;
}

void HeapDestroy(Heap* ph)
{
	assert(ph);

	free(ph->arr);
	ph->size = ph->capacity = 0;
}